from collections import deque


class MazeSolution:
    def __init__(self, maze):
        self.maze = maze
        self.length = len(maze)
        self.width = len(maze[0])
        self.hight = len(maze[0][0])

    def has_path(self, maze, start, destination) -> bool:
        return self.bfs(maze, start, destination)

    def bfs(self, maze, start, target):
        q = deque()
        visited = []

        for i in range(self.length):
            for j in range(self.width):
                for k in range(self.hight):
                    if maze[i][j][k] == True:
                        visited.append([i, j, k])
        q.append(start)
        visited.append(start)

        while q:
            sz = len(q)
            for i in range(sz):
                cur = q.popleft()
                if cur == target:
                    return True

                self.get_neighbor_paras()
                for x in self.neighbors(cur):
                    if x not in visited:
                        q.append(x)
                        visited.append(x)
        return False

    def set_neighbor_paras(self, **kwargs):
        self.neighbor_paras = kwargs
        return self.neighbor_paras

    def get_neighbor_paras(self):
        return self.neighbor_paras

    def neighbors(self, pos):
        neighbors = []

        left = self.neighbor_paras["left"]
        right = self.neighbor_paras["right"]
        up = self.neighbor_paras["up"]
        down = self.neighbor_paras["down"]
        forward = self.neighbor_paras["forward"]
        backward = self.neighbor_paras["backward"]
        #self.set_neighbors_parameters()
        if self.move_left(pos, left) is not None:
            neighbors.append(self.move_left(pos, left))
        if self.move_right(pos, right) is not None:
            neighbors.append(self.move_right(pos, right))
        if self.move_up(pos, up) is not None:
            neighbors.append(self.move_up(pos, up))
        if self.move_down(pos, down) is not None:
            neighbors.append(self.move_down(pos, down))
        if self.move_forward(pos, forward) is not None:
            neighbors.append(self.move_forward(pos, forward))
        if self.move_backward(pos, backward) is not None:
            neighbors.append(self.move_backward(pos, backward))
        return neighbors

    #def set_neighbors_parameters(self,**kwargs):


    def move_left(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if col > 0:
            if self.maze[row][col - step][depth]:
                return
            t = 0
            while (not self.maze[row][col - 1][depth]) and col > 0 and t < step:
                t += 1
                col -= 1
            return [row, col, depth]

    def move_right(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if col < self.width - 1:
            if self.maze[row][col + step][depth] or col == self.width - 1:
                return
            t = 0
            while col < self.width - 1 and (not self.maze[row][col + 1][depth]) and t < step:
                t += 1
                col += 1
            return [row, col, depth]

    def move_up(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if row > 0:
            if self.maze[row - step][col][depth]:
                return
            t = 0
            while (not self.maze[row - 1][col][depth]) and row > 0 and t < step:
                t += 1
                row -= 1
            return [row, col, depth]

    def move_down(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if row < self.length - 1:
            if self.maze[row + step][col][depth] or row == self.length - 1:
                return
            t = 0
            while row < self.length - 1 and not self.maze[row + 1][col][depth] and t < step:
                t += 1
                row += 1
            return [row, col, depth]

    def move_forward(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if depth < self.hight - 1:
            if self.maze[row][col][depth + step] or depth == self.hight - 1:
                return
            t = 0
            while depth < self.hight - 1 and not self.maze[row][col][depth + 1] and t < step:
                t += 1
                depth += 1
            return [row, col, depth]

    def move_backward(self, pos, step):
        row = pos[0]
        col = pos[1]
        depth = pos[2]
        if depth > 0:
            if self.maze[row][col][depth - step]:
                return
            t = 0
            while (not self.maze[row][col][depth - 1]) and depth > 0 and t < step:
                t += 1
                depth -= 1
            return [row, col, depth]

    def get_visited(self):
        return self.visited
